#ifndef UTILS_INTERVALS_HPP
#define UTILS_INTERVALS_HPP

#include <list>
#include <utility>
#include <algorithm>
#include <iterator>
#include <cassert>

namespace utils
{


/// \brief It provides utility methods that are used by the interval set while performing various operations.
/// \details
///		This structure has the role of an adaptor. It adapts the interval type to the interval set. This default 
///		implementation is dedicated to native types, which provide "less-than" operator.
template< class T>
struct interval_traits
{
	/// \brief The type of the values in an interval.
	typedef T value_type;

	/// \brief The interval type.
	/// \details
	///		The described interval is considered to include the begin value and to exclude the end value.
	typedef std::pair< T, T> interval_type;
	
	/// \brief It gets the first value of the interval.
	static const T& begin( const interval_type& i) { return i.first; }

	/// \brief It gets the first value after the end of the interval.
	static const T& end( const interval_type& i) { return i.second; }
	
	/// \brief It creates an interval out of the two provided boundaries.
	static interval_type make_interval( const value_type& b, const value_type& e) { return std::make_pair( b, e); }

	/// \brief It compares two values of an interval.
	static bool less( const value_type& op1, const value_type& op2) { return op1 < op2; }

	/// \brief It compares the begin values of two intervals.
	static bool start_less( const interval_type& op1, const interval_type& op2) { return less( begin( op1), begin(op2)); }

	/// \brief It checks whether the given value is contained in the given interval.
	static bool interval_contains( const interval_type& i, const value_type v) 
	{
		return !less( v, begin( i)) && less( v, end( i));
	}
};

/// \brief It holds a set of intervals, ordered by the start value. The intervals don't overlap.
/// \param T the type of the values in the intervals.
/// \param Traits the utility class providing the basic operations related to intervals. It has the role of adaptor.
template< class T, class Traits = interval_traits< T> >
class interval_set
{
public:
	typedef Traits traits_type;
	typedef typename traits_type::value_type value_type;
	typedef typename traits_type::interval_type interval_type;
	typedef std::list< interval_type> interval_collection;
	typedef typename interval_collection::const_iterator const_iterator;
	typedef typename interval_collection::size_type size_type;

public:
	/// \brief It intesects the interval managed by this class with the given interval. Only the common ranges will 
	///		remain in the collection.
	void intersect( const interval_type& interval)
	{
		this->intersect( traits_type::begin( interval), traits_type::end( interval));
	}


	/// \brief It intesects the interval managed by this class with the given interval. Only the common ranges will 
	///		remain in the collection.
	void intersect( const value_type& b, const value_type& e)
	{
		assert( traits_type::less( b, e));
		interval_collection result;
		interval_collection::const_iterator curI = intervals_.begin(), endI = intervals_.end();
		while( curI != endI)
		{
			value_type curStart = traits_type::begin( *curI),
				curEnd = traits_type::end( *curI);
			if( traits_type::less( curEnd, b) || 
				traits_type::less( e, curStart))
			{
				++curI;
				continue;
			}

			curStart = (traits_type::less( curStart, b)) ? b : curStart;
			curEnd = (traits_type::less( e, curEnd)) ? e : curEnd;
			// Assume that the curStart <= curEnd
			assert( !traits_type::less( curEnd, curStart));
			if( traits_type::less( curStart, curEnd))
			{
				// With this check, the empty intersection was excluded, so the intersection result can be added.
				result.push_back( traits_type::make_interval( curStart, curEnd));
			}
			++curI;
		}
		intervals_.swap( result);
	}

	void subtract( const interval_type& interval)
	{
		this->subtract( traits_type::begin( interval), traits_type::end( interval));
	}

	void subtract( const value_type& start, const value_type& end)
	{
		interval_collection result;
		interval_collection::const_iterator curI = intervals_.begin(), endI = intervals_.end();

		// It iterates through the current intervals, adding to the new interval collection the intervals not 
		//	intersecting the given one. The intersections are either ignored (case of intervals completely contained in 
		//	the given interval) or adjusted (in case of partial intersection).
		while( curI != endI)
		{
			value_type curStart = traits_type::start( *curI),
				curEnd = traits_type::end( *curI);
			// Skip when interval contained in the start, end interval
			if( !traits_type::less( curStart, start) && !traits_type::less( end, curEnd))
				continue;

			result.push_back( traits_type::make_interval( *curI));
			++curI;
		}

		if( curI != endI)
		{
			// TODO: Continue
		}
		assert(false);
	}

	void merge( const interval_type& interval)
	{
		this->merge( traits_type::begin( interval), traits_type::end( interval));
	}

	void merge( const value_type& start, const value_type& end)
	{
		interval_collection result;
		interval_collection::iterator curIter = intervals_.begin(),
			endIter = intervals_.end();

		this->merge( result, start, end, curIter, endIter);

		// Duplicate intervals after reaching end:
		while( curIter != endIter)
		{
			result.push_back( *curIter);
			++curIter;
		}

		intervals_.swap( result);
	}

	void merge( const interval_set< T, Traits>& op2)
	{
		interval_collection overlappedResult;
		std::merge( 
			intervals_.begin(), intervals_.end(), 
			op2.intervals_.begin(), op2.intervals_.end(), 
			std::back_inserter( overlappedResult), &traits_type::start_less);

		interval_collection result;
		interval_collection::const_iterator curI = overlappedResult.begin(), endI = overlappedResult.end();
		while( curI != endI)
		{
			value_type curStart = traits_type::begin( *curI)
					, curEnd = traits_type::end( *curI);
			
			// Iterate while two intervals overlap
			++curI;
			while( curI != endI && !traits_type::less( curEnd, traits_type::begin( *curI)))
			{
				curEnd = (traits_type::less( curEnd, traits_type::end( *curI))) ? traits_type::end( *curI) : curEnd;
				++curI;
			}
	
			result.push_back( traits_type::make_interval( curStart, curEnd));
		}
		
		intervals_.swap( result);
	}

	const_iterator begin() const { return intervals_.begin(); }
	const_iterator end() const { return intervals_.end(); }
	size_type size() const { return intervals_.size(); }
	void clear() { intervals_.clear(); }
	bool empty() const { return intervals_.empty(); }

	void swap( interval_set& op)
	{
		intervals_.swap( op.intervals_);
	}

	static value_type interval_start( const interval_type& interval) { return traits_type::begin( interval); }
	static value_type interval_end( const interval_type& interval) { return traits_type::end( interval); }

private:
	interval_collection intervals_;

private:
	void merge( interval_collection& result, const value_type& start, const value_type& end, const_iterator& curIter, const const_iterator& endIter)
	{
		// Duplicate intervals before reaching start (meaning the current interval's start is less than the start
		while( curIter != endIter && traits_type::less( traits_type::end( *curIter), start) )
		{
			result.push_back( *curIter);
			++curIter;
		}
		// Now, start should be involved:
		if( curIter == endIter)
		{
			// Insertion at the end:
			result.push_back( traits_type::make_interval( start, end));
		}
		else
		{
			value_type curStart = traits_type::less( traits_type::begin( *curIter), start) ? traits_type::begin( *curIter) : start,
				curEnd = end;
			// Look for end, skipping the intervals that are fully contained between start and end.
			while( curIter != endIter)
			{
				if( traits_type::less( end, traits_type::begin( *curIter)))
				{
					curEnd = end;
					break;
				}
				else if( traits_type::interval_contains( *curIter, end))
				{
					// End is inside the period
					curEnd = traits_type::end( *curIter);
					++curIter;
					break;
				}
				++curIter;
			}
			result.push_back( traits_type::make_interval( curStart, curEnd));
		}
	}

};

} // namespace utils

#endif // UTILS_INTERVALS_HPP
